<?php
/**
 * @title 75. 颜色分类 - 双指针1次遍历-2
 * @author start2004
 */

// ini_set("memory_limit", "128M");

class Solution {

    /**
     * @param Integer[] $nums
     * @return NULL
     */
    function sortColors(&$nums) {
        /**
         * @since 2020-10-12 指针0, 指针1位置
         */
        $p0 = 0;
        $p1 = 0;

        /**
         * @since 2020-10-13 1次遍历
         */
        for($i=0; $i<count($nums); $i++){
            // echo "i={$i}, ";

            /**
             * @since 2020-10-13 p1交换, 不可能交换个0回来
             */
            if($nums[$i] == 1){
                $nums[$i] = $nums[$p1];
                $nums[$p1] = 1;
                $p1++;
            } elseif($nums[$i] == 0) {
                /**
                 * @since 2020-10-13 可能会交换个1回来, 指针不变
                 */
                if($p0 != $i){
                    $nums[$i] = $nums[$p0];
                    $nums[$p0] = 0;
                    $i--;
                } else {}
                $p0++;

                /**
                 * @since 2020-10-13 p1指针必须大于等于p0指针
                 */
                $p1 = max($p0, $p1);
            } else {
                /**
                 * @since 2020-10-13 不操作
                 */
            }

            // echo "nums=[", implode(",", $nums) ,"], p0={$p0}, p1={$p1}", PHP_EOL;
        }

        /**
         * @return
         */
        return $nums;
    }
}



/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.05_6.php
 */
$datas = [
    [0],
    [2,0,2,1,1,0],
    // [1,2,2,2,2,0,0,0,1,1],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->sortColors($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
